//===--- DependencyGraph.cpp - Track intra-module dependencies ------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "polarphp/basic/ReferenceDependencyKeys.h"
#include "polarphp/basic/Statistic.h"
#include "polarphp/driver/DependencyGraph.h"
#include "polarphp/demangling/Demangle.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/Support/YAMLParser.h"

using namespace polar;

enum class DependencyGraphImpl::DependencyKind : uint8_t {
   TopLevelName = 1 << 0,
   DynamicLookupName = 1 << 1,
   NominalType = 1 << 2,
   NominalTypeMember = 1 << 3,
   ExternalFile = 1 << 4,
};
enum class DependencyGraphImpl::DependencyFlags : uint8_t {
   IsCascading = 1 << 0
};

class DependencyGraphImpl::MarkTracerImpl::Entry {
public:
   const void *Node;
   StringRef Name;
   DependencyMaskTy KindMask;
};

DependencyGraphImpl::MarkTracerImpl::MarkTracerImpl(UnifiedStatsReporter *Stats)
   : Stats(Stats) {}
DependencyGraphImpl::MarkTracerImpl::~MarkTracerImpl() = default;

using LoadResult = DependencyGraphImpl::LoadResult;
using DependencyKind = DependencyGraphImpl::DependencyKind;
using DependencyCallbackTy = LoadResult(StringRef, DependencyKind, bool);
using InterfaceHashCallbackTy = LoadResult(StringRef);

static LoadResult
parseDependencyFile(llvm::MemoryBuffer &buffer,
                    llvm::function_ref<DependencyCallbackTy> providesCallback,
                    llvm::function_ref<DependencyCallbackTy> dependsCallback,
                    llvm::function_ref<InterfaceHashCallbackTy> interfaceHashCallback) {
   namespace yaml = llvm::yaml;

   // FIXME: Switch to a format other than YAML.
   llvm::SourceMgr SM;
   yaml::Stream stream(buffer.getMemBufferRef(), SM);
   auto I = stream.begin();
   if (I == stream.end() || !I->getRoot())
      return LoadResult::HadError;

   auto *topLevelMap = dyn_cast<yaml::MappingNode>(I->getRoot());
   if (!topLevelMap) {
      if (isa<yaml::NullNode>(I->getRoot()))
         return LoadResult::UpToDate;
      return LoadResult::HadError;
   }

   LoadResult result = LoadResult::UpToDate;
   SmallString<64> scratch;

   // After an entry, we know more about the node as a whole.
   // Update the "result" variable above.
   // This is a macro rather than a lambda because it contains a return.
#define UPDATE_RESULT(update) switch (update) {\
    case LoadResult::HadError: \
      return LoadResult::HadError; \
    case LoadResult::UpToDate: \
      break; \
    case LoadResult::AffectsDownstream: \
      result = LoadResult::AffectsDownstream; \
      break; \
    } \

   // FIXME: LLVM's YAML support does incremental parsing in such a way that
   // for-range loops break.
   for (auto i = topLevelMap->begin(), e = topLevelMap->end(); i != e; ++i) {
      if (isa<yaml::NullNode>(i->getValue()))
         continue;

      auto *key = dyn_cast<yaml::ScalarNode>(i->getKey());
      if (!key)
         return LoadResult::HadError;
      StringRef keyString = key->getValue(scratch);

      using namespace referencedependencykeys;

      if (keyString == interfaceHash) {
         auto *value = dyn_cast<yaml::ScalarNode>(i->getValue());
         if (!value)
            return LoadResult::HadError;

         StringRef valueString = value->getValue(scratch);
         UPDATE_RESULT(interfaceHashCallback(valueString));

      } else {
         enum class DependencyDirection : bool {
            Depends,
            Provides
         };
         using KindPair = std::pair<DependencyKind, DependencyDirection>;

         KindPair dirAndKind = llvm::StringSwitch<KindPair>(key->getValue(scratch))
            .Case(dependsTopLevel,
                  std::make_pair(DependencyKind::TopLevelName,
                                 DependencyDirection::Depends))
            .Case(dependsNominal,
                  std::make_pair(DependencyKind::NominalType,
                                 DependencyDirection::Depends))
            .Case(dependsMember,
                  std::make_pair(DependencyKind::NominalTypeMember,
                                 DependencyDirection::Depends))
            .Case(dependsDynamicLookup,
                  std::make_pair(DependencyKind::DynamicLookupName,
                                 DependencyDirection::Depends))
            .Case(dependsExternal,
                  std::make_pair(DependencyKind::ExternalFile,
                                 DependencyDirection::Depends))
            .Case(providesTopLevel,
                  std::make_pair(DependencyKind::TopLevelName,
                                 DependencyDirection::Provides))
            .Case(providesNominal,
                  std::make_pair(DependencyKind::NominalType,
                                 DependencyDirection::Provides))
            .Case(providesMember,
                  std::make_pair(DependencyKind::NominalTypeMember,
                                 DependencyDirection::Provides))
            .Case(providesDynamicLookup,
                  std::make_pair(DependencyKind::DynamicLookupName,
                                 DependencyDirection::Provides))
            .Default(std::make_pair(DependencyKind(),
                                    DependencyDirection::Depends));
         if (dirAndKind.first == DependencyKind())
            return LoadResult::HadError;

         auto *entries = dyn_cast<yaml::SequenceNode>(i->getValue());
         if (!entries)
            return LoadResult::HadError;

         if (dirAndKind.first == DependencyKind::NominalTypeMember) {
            // Handle member dependencies specially. Rather than being a single
            // string, they come in the form ["{MangledBaseName}", "memberName"].
            for (yaml::Node &rawEntry : *entries) {
               bool isCascading = rawEntry.getRawTag() != "!private";

               auto *entry = dyn_cast<yaml::SequenceNode>(&rawEntry);
               if (!entry)
                  return LoadResult::HadError;

               auto iter = entry->begin();
               auto *base = dyn_cast<yaml::ScalarNode>(&*iter);
               if (!base)
                  return LoadResult::HadError;
               ++iter;

               auto *member = dyn_cast<yaml::ScalarNode>(&*iter);
               if (!member)
                  return LoadResult::HadError;
               ++iter;

               // FIXME: LLVM's YAML support doesn't implement == correctly for end
               // iterators.
               assert(!(iter != entry->end()));

               bool isDepends = dirAndKind.second == DependencyDirection::Depends;
               auto &callback = isDepends ? dependsCallback : providesCallback;

               // Smash the type and member names together so we can continue using
               // StringMap.
               SmallString<64> appended;
               appended += base->getValue(scratch);
               appended.push_back('\0');
               appended += member->getValue(scratch);

               UPDATE_RESULT(callback(appended.str(), dirAndKind.first,
                                      isCascading));
            }
         } else {
            for (const yaml::Node &rawEntry : *entries) {
               auto *entry = dyn_cast<yaml::ScalarNode>(&rawEntry);
               if (!entry)
                  return LoadResult::HadError;

               bool isDepends = dirAndKind.second == DependencyDirection::Depends;
               auto &callback = isDepends ? dependsCallback : providesCallback;

               UPDATE_RESULT(callback(entry->getValue(scratch), dirAndKind.first,
                                      entry->getRawTag() != "!private"));
            }
         }
      }
   }

   return result;
}

LoadResult DependencyGraphImpl::loadFromPath(const void *node, StringRef path) {
   auto buffer = llvm::MemoryBuffer::getFile(path);
   if (!buffer)
      return LoadResult::HadError;
   return loadFromBuffer(node, *buffer.get());
}

LoadResult
DependencyGraphImpl::loadFromString(const void *node, StringRef data) {
   auto buffer = llvm::MemoryBuffer::getMemBuffer(data);
   return loadFromBuffer(node, *buffer);
}

LoadResult DependencyGraphImpl::loadFromBuffer(const void *node,
                                               llvm::MemoryBuffer &buffer) {
   auto &provides = Provides[node];

   auto dependsCallback = [this, node](StringRef name, DependencyKind kind,
                                       bool isCascading) -> LoadResult {
      if (kind == DependencyKind::ExternalFile)
         ExternalDependencies.insert(name);

      auto &entries = Dependencies[name];
      auto iter = std::find_if(entries.first.begin(), entries.first.end(),
                               [node](const DependencyEntryTy &entry) -> bool {
                                  return node == entry.node;
                               });

      DependencyFlagsTy flags;
      if (isCascading)
         flags |= DependencyFlags::IsCascading;

      if (iter == entries.first.end()) {
         entries.first.push_back({node, kind, flags});
      } else {
         iter->kindMask |= kind;
         iter->flags |= flags;
      }

      if (isCascading && (entries.second & kind))
         return LoadResult::AffectsDownstream;
      return LoadResult::UpToDate;
   };

   auto providesCallback =
      [&provides](StringRef name, DependencyKind kind,
                  bool isCascading) -> LoadResult {
         assert(isCascading);
         auto iter = std::find_if(provides.begin(), provides.end(),
                                  [name](const ProvidesEntryTy &entry) -> bool {
                                     return name == entry.name;
                                  });

         if (iter == provides.end())
            provides.push_back({name, kind});
         else
            iter->kindMask |= kind;

         return LoadResult::UpToDate;
      };

   auto interfaceHashCallback = [this, node](StringRef hash) -> LoadResult {
      auto insertResult = InterfaceHashes.insert(std::make_pair(node, hash));

      if (insertResult.second) {
         // Treat a newly-added hash as up-to-date. This includes the initial
         // load of the file.
         return LoadResult::UpToDate;
      }

      auto iter = insertResult.first;
      if (hash != iter->second) {
         iter->second = hash;
         return LoadResult::AffectsDownstream;
      }

      return LoadResult::UpToDate;
   };

   return parseDependencyFile(buffer, providesCallback, dependsCallback,
                              interfaceHashCallback);
}

void DependencyGraphImpl::markExternal(SmallVectorImpl<const void *> &visited,
                                       StringRef externalDependency) {
   forEachUnmarkedJobDirectlyDependentOnExternalPHPdeps(
      externalDependency, [&](const void *node) {
         visited.push_back(node);
         markTransitive(visited, node);
      });
}

void DependencyGraphImpl::forEachUnmarkedJobDirectlyDependentOnExternalPHPdeps(
   StringRef externalPHPDeps, function_ref<void(const void *node)> fn) {
   auto allDependents = Dependencies.find(externalPHPDeps);
   assert(allDependents != Dependencies.end() && "not a dependency!");
   allDependents->second.second |= DependencyKind::ExternalFile;
   for (const auto &dependent : allDependents->second.first) {
      if (!dependent.kindMask.contains(DependencyKind::ExternalFile))
         continue;
      if (isMarked(dependent.node))
         continue;
      assert(dependent.flags & DependencyFlags::IsCascading);
      fn(dependent.node);
   }
}

void
DependencyGraphImpl::markTransitive(SmallVectorImpl<const void *> &visited,
                                    const void *node, MarkTracerImpl *tracer) {
   assert(Provides.count(node) && "node is not in the graph");
   llvm::SpecificBumpPtrAllocator<MarkTracerImpl::Entry> scratchAlloc;

   struct WorklistEntry {
      ArrayRef<MarkTracerImpl::Entry> Reason;
      const void *Node;
      bool IsCascading;
   };

   SmallVector<WorklistEntry, 16> worklist;
   SmallPtrSet<const void *, 16> visitedSet;

   auto addDependentsToWorklist = [&](const void *next,
                                      ArrayRef<MarkTracerImpl::Entry> reason) {
      auto allProvided = Provides.find(next);
      if (allProvided == Provides.end())
         return;

      for (const auto &provided : allProvided->second) {
         auto allDependents = Dependencies.find(provided.name);
         if (allDependents == Dependencies.end())
            continue;

         if (allDependents->second.second.contains(provided.kindMask))
            continue;

         // Record that we've traversed this dependency.
         allDependents->second.second |= provided.kindMask;

         for (const auto &dependent : allDependents->second.first) {
            if (dependent.node == next)
               continue;
            auto intersectingKinds = provided.kindMask & dependent.kindMask;
            if (!intersectingKinds)
               continue;
            if (isMarked(dependent.node))
               continue;
            bool isCascading{dependent.flags & DependencyFlags::IsCascading};

            MutableArrayRef<MarkTracerImpl::Entry> newReason;
            if (tracer) {
               tracer->countStatsForNodeMarking(intersectingKinds, isCascading);
               newReason = {scratchAlloc.Allocate(reason.size()+1), reason.size()+1};
               std::uninitialized_copy(reason.begin(), reason.end(),
                                       newReason.begin());
               new (&newReason.back()) MarkTracerImpl::Entry({next, provided.name,
                                                              intersectingKinds});
            }
            worklist.push_back({ newReason, dependent.node, isCascading });
         }
      }
   };

   auto record = [&](WorklistEntry next) {
      if (!visitedSet.insert(next.Node).second)
         return;
      visited.push_back(next.Node);
      if (tracer) {
         auto &savedReason = tracer->Table[next.Node];
         savedReason.clear();
         savedReason.append(next.Reason.begin(), next.Reason.end());
      }
   };

   // Always mark through the starting node, even if it's already marked.
   markIntransitive(node);
   addDependentsToWorklist(node, {});

   while (!worklist.empty()) {
      auto next = worklist.pop_back_val();

      // Is this a non-cascading dependency?
      if (!next.IsCascading) {
         if (!isMarked(next.Node))
            record(next);
         continue;
      }

      addDependentsToWorklist(next.Node, next.Reason);
      if (!markIntransitive(next.Node))
         continue;
      record(next);
   }
}

void DependencyGraphImpl::MarkTracerImpl::countStatsForNodeMarking(
   const OptionSet<DependencyKind> &Kind, bool IsCascading) const {

   if (!Stats)
      return;

   auto &D = Stats->getDriverCounters();
   if (IsCascading) {
      if (Kind & DependencyKind::TopLevelName)
         D.DriverDepCascadingTopLevel++;
      if (Kind & DependencyKind::DynamicLookupName)
         D.DriverDepCascadingDynamic++;
      if (Kind & DependencyKind::NominalType)
         D.DriverDepCascadingNominal++;
      if (Kind & DependencyKind::NominalTypeMember)
         D.DriverDepCascadingMember++;
      if (Kind & DependencyKind::NominalTypeMember)
         D.DriverDepCascadingExternal++;
   } else {
      if (Kind & DependencyKind::TopLevelName)
         D.DriverDepTopLevel++;
      if (Kind & DependencyKind::DynamicLookupName)
         D.DriverDepDynamic++;
      if (Kind & DependencyKind::NominalType)
         D.DriverDepNominal++;
      if (Kind & DependencyKind::NominalTypeMember)
         D.DriverDepMember++;
      if (Kind & DependencyKind::NominalTypeMember)
         D.DriverDepExternal++;
   }
}

void DependencyGraphImpl::MarkTracerImpl::printPath(
   raw_ostream &out,
   const void *item,
   llvm::function_ref<void (const void *)> printItem) const {
   for (const Entry &entry : Table.lookup(item)) {
      out << "\t";
      printItem(entry.Node);
      if (entry.KindMask.contains(DependencyKind::TopLevelName)) {
         out << " provides top-level name '" << entry.Name << "'\n";

      } else if (entry.KindMask.contains(DependencyKind::NominalType)) {
         SmallString<64> name{entry.Name};
         if (name.front() == 'P')
            name.push_back('_');
         out << " provides type '"
         // TODO
//             << polar::demangling::demangleTypeAsString(name.str())
             << "'\n";

      } else if (entry.KindMask.contains(DependencyKind::NominalTypeMember)) {
         SmallString<64> name{entry.Name};
         size_t splitPoint = name.find('\0');
         assert(splitPoint != StringRef::npos);

         StringRef typePart;
         if (name.front() == 'P') {
            name[splitPoint] = '_';
            typePart = name.str().slice(0, splitPoint+1);
         } else {
            typePart = name.str().slice(0, splitPoint);
         }
         StringRef memberPart = name.str().substr(splitPoint+1);

         if (memberPart.empty()) {
            out << " provides non-private members of type '"
            /// TODO
//                << polar::demangling::demangleTypeAsString(typePart)
                << "'\n";
         } else {
            out << " provides member '" << memberPart << "' of type '"
                /// TODO
//                << polar::demangling::demangleTypeAsString(typePart)
                << "'\n";
         }
      } else if (entry.KindMask.contains(DependencyKind::DynamicLookupName)) {
         out << " provides AnyObject member '" << entry.Name << "'\n";

      } else {
         llvm_unreachable("not a dependency kind between nodes");
      }
   }
}
